46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
思路及算法
全排列是经典的回溯算法问题
推荐看这篇文章入门 回溯算法解题套路框架
以[1,2,3]举例, 下图就是它的『决策树』
以『深度优先』遍历此树
第一次选择1， 之后有两种选择——2和3
接着，我们选择2，然后继续往下选择3，此时的『路径』为[1, 2, 3]，是一种组合排列方式
在『深度遍历』中，如果“触底”， 自然会向上返回，而这一步就是『回溯』
当我们重新返回1时，还是那两个选择——2和3
2已经走过了，所以此时我们选择3往下走
大佬们，总结了一个『回溯算法』的核心框架
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择（回溯）
代码
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
size = len(nums)
res = []
def backtrack(nnn, track):
"""
:params nums: 待选择列表
:params track: 路径(已经被选择的)
"""
if len(track) == size:
res.append(track[:])
return
for n in nnn:
# 从待选择列表里拿出数据
if n in track:
continue
# 做选择
track.append(n)
# 继续下一层决策
backtrack(nnn, track)
# 回溯
track.pop()
backtrack(nums, [])
return res
47. 全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
思路及算法
听大佬们的经验，做『回溯算法』的题，最好就是先把决策树画出来，方便我们观察然后判断选择判断条件进行剪枝
因为存在重复元素，所以我们需要知道所有元素被选择的状态。如果已经被选择了，则不能再选择使用。初始化，所有的元素都没有被选择
used = [False for _ in len(nums)]
举例解释：
[1, 1, 2]
每次选择都会遍历这个数组
当选择第一个1时，下一次选择第二个数，仍然是从索引为0处开始的。
此时索引为0的元素是被记录为『已被选择』，所以就选择第二个1了
- 剪枝
通过上图不难发现，路径的某个元素一样，那么后续的都会是一样的（红色标记），这种情况只算作一次，其余的都算是重复项
怎么判断重复项？
如果上一个路径的选择，与此次路径选择一直，则跳过本次路径的选择
即： nums[i-1] == nums[i] 满足此条件，则说明当前i起头的这条路径已经是重复项
现在仍需要完善这个剪枝条件：
-
i必须大于0 -
nums[i-1]没有被选择，即used[i-1] = False
具体解释下第二点，在标记的这条路径上，当选择到第二个1时满足 nums[i-1] == nums[i] ，但是这个时候并不需要我们剪枝
注意： 为了方便剪枝，num需要做一次排序
代码
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
result = []
size = len(nums)
def drf(sorted_nums, track, used):
# 当前决策树的深度，即当前路径的长度
curr_depth = len(track)
# 长度一致，则可以加入结果数组中
if curr_depth == size:
result.append(track[:])
return
# 从列表内选择元素出来
for i in size:
# 判断当前元素是否已被选择
if not used[i]:
# 判断当前元素，是不是重复路径的开始
if i > 0 and sorted[i-1] == sorted[i] and not used[i-1]:
continue
# 将当前这个选择放入路径
track.append(sorted_nums[i])
# 将当前元素标记为已使用
used[i] = True
# 进入下一次层，继续选择
drf(sorted_nums, track, used)
# 回退选择
track.pop()
# 当前元素已被回溯，标记未被使用
used[i] = False
nums = sorted(nums)
drf(nums, [], [False for _ in size])
return result
参考文章: